package class23;

import java.util.HashMap;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class LongestSumSubArrayLength3 {

    public static int maxLength(int[] arr,int K){
        if (arr == null || arr.length == 0)
            return 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int len = 0;
        int sum = 0;
        for (int i = 0;i<arr.length;i++){
            sum += arr[i];
            if (map.containsKey(sum - K)){
                len = Math.max(i-map.get(sum-K),len);
            }
            if (!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
        return len;
    }

    public static int right(int[] arr,int K){
        int max = 0;
        for (int i=0;i<arr.length;i++){
            for (int j = i;j<arr.length;j++){
                if (valid(arr,i,j,K)){
                    max = Math.max(max,j-i+1);
                }
            }
        }
        return max;
    }

    public static boolean valid(int[] arr,int L,int R,int K){
        int sum  = 0;
        for (int i = L;i<=R;i++){
            sum += arr[i];
        }
        return sum == K;
    }

    public static int[] generateRandomArray(int size,int value){
        int[] ans = new int[(int)(Math.random()*size)+1];
        for (int i = 0;i<ans.length;i++){
            ans[i] = (int)(Math.random()*value)-(int)(Math.random()*value);
        }
        return ans;
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 500000;
        System.out.println("test begin!");
        for (int i =0;i<testTime;i++){
            int[] arr = generateRandomArray(len,value);
            int K = (int)(Math.random()*value)-(int)(Math.random()*value);
            int ans1 = maxLength(arr,K);
            int ans2 = right(arr,K);
            if (ans1 != ans2){
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("test end!");
    }
}
